#include <algorithm>
#include <cstdint>
#include <iostream>
#include <istream>
#include <vector>

using ll = int64_t;

int main(){
    std::iostream::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ll t,m;
    std::cin>>t>>m;
    std::vector<ll> dp(t+1);
    for(ll i=1;i<=m;i++){
        ll w,v;
        std::cin>>w>>v;
        for(ll j=w;j<=t;j++){
            dp[j]=std::max(dp[j],dp[j-w]+v);
        }
    }
    std::cout<<dp[t]<<"\n";
}